`include "chunjun_define.sv" 
`include "chunjun_lib_define.sv" 

//===================================================================
// Date        : 2023-08-05
// Description : 
//
// Leading zero count.
//  - DIRECTION = 1: leading zero count.
//  - DIRECTION = 0: trailing zero count.
//
// We build a binary tree to represent the implementation of LZC.
// level represents the level of the binary tree, range: 0 ~ log2(WIDTH)
//
// level: 0                                        1
//                                           /            \
// level: 1                               1                 1
//                                     /     \           /     \
// level: 2                          1         1        1        1
//                                 /   \     /   \    /   \     /  \  
// ...                           ...     ...    ...    ...    ...   ...
//                               / \  / \  / \  / \  / \  / \  / \  / \
// level: log2(WIDTH)      WIDTH-1  ...  ...    9 8  7 6  5 4  3 2  1 0
//
//===================================================================

module wing_cbb_lzc #(
  parameter WIDTH     = 8,
  parameter DIRECTION = 1,   // 1: leading zero detect; 0: trailing zero detect
  parameter IDX_W     = $clog2(WIDTH),
  parameter INVERT    = 0
) (
  input  logic [WIDTH-1:0]      vec_i,
  output logic [IDX_W-1:0]      cnt_o,
  output logic                  empty_o
);


if (WIDTH == 1) begin : gen_degenerate_lzc
 
  assign cnt_o[0] = !vec_i[0];
  assign empty_o  = !vec_i[0];

end else begin : gen_lzc
 
  localparam WIDTH_ROUND_W = 2**IDX_W;

// sel_nodes   : each sel_nodes[i] indicates the node itself and its child node have '1' or not. 
// index nodes : each index_nodes[i] indicates the selected zero count .
// index_lut   : lookup-table for zero count.
  logic [WIDTH_ROUND_W-2:0]             sel_nodes;
  logic [WIDTH_ROUND_W-2:0][IDX_W-1:0]  index_nodes;
  logic [WIDTH-1:0][IDX_W-1:0]          index_lut;
  logic [WIDTH-1:0]                     vector;

  for (genvar j = 0; j < WIDTH; j++) begin : g_index_lut
      assign index_lut[j] = j;
  end //g_index_lut

   if(INVERT == 1 )begin: LOC
    assign vector = ~vec_i;
  end else begin: LZC
    assign vector =  vec_i;
  end

  if (DIRECTION == 0) begin : trailing_cnt

// level: 0                                     sel[0]
//                                           /            \
// level: 1                           sel[1]            sel[2]
//                                     /     \           /     \
// level: 2                      sel[3]    sel[4]   sel[5]   sel[6]
//                                 /   \     /   \    /   \     /  \  
//                          vec_i[0]   [1] [2]  [3] [4]   [5] [6]  [7] 
//
//                      index_lut[0]   [1] [2]  [3] [4]   [5] [6]  [7] 

    for (genvar level = 0; level < IDX_W; level++) begin : g_levels
      if (level == IDX_W - 1) begin : g_last_level

// For the last level, adjacent 2 bit are compared to generate upper level results.
// If the input vector width is not power-of-two, there will be three situations.
// Let's take WIDTH = 5, input = 5'b01101 as an example.
// level: 0                                        1
//                                           /            \
// level: 1                               1                 1
//                                     /     \           /     \
// level: 2                          0         1        1        1
//                                 /   \     /   \    /   \     /  \  
// level: 3                       0     0   0     1  0     1   1    0
//
// index:                         7     6   5     4  3     2   1    0
// 
// - Situation 1 (index 1-0, index 3-2): 
//    - two successive indexs are still in the vector
// - Situation 2 (index 5-4):
//    - only the first index is still in the vector, another index is out of vector, choose the first index.
// - Situation 3 (index 7-6):
//    - index is out of range, sel_node tie 0 

        for (genvar k = 0; k < 2 ** level; k++) begin : g_iter
          // if two successive indexs are still in the vector...
          if (k * 2 < WIDTH - 1) begin : g_idx_inside
            assign sel_nodes  [2 ** level - 1 + k] = vector[k * 2    ] | 
                                                     vector[k * 2 + 1] ;
            assign index_nodes[2 ** level - 1 + k] = (vector[k * 2] == 1'b1) ? index_lut[k * 2] :
                                                                              index_lut[k * 2 + 1];
 
          // if only the first index is still in the vector, another index is out of vector, choose the first index.
          end else if (k * 2 == WIDTH - 1) begin : g_idx_border
            assign sel_nodes  [2 ** level - 1 + k] = vector[k * 2];
            assign index_nodes[2 ** level - 1 + k] = index_lut[k * 2];
 
          // if index is out of range, sel_node tie 0 
          // (k * 2 > WIDTH - 1) 
          end else begin : g_idx_out
            assign sel_nodes  [2 ** level - 1 + k] = 1'b0;
            assign index_nodes[2 ** level - 1 + k] = '0;
          end
        end

      end else begin : g_upper_level
        for (genvar l = 0; l < 2 ** level; l++) begin : g_idx_sel
          assign sel_nodes[2 ** level - 1 + l] = sel_nodes[2 ** (level + 1) - 1 + l * 2    ] | 
                                                 sel_nodes[2 ** (level + 1) - 1 + l * 2 + 1] ;
          assign index_nodes[2 ** level - 1 + l] = (sel_nodes[2 ** (level + 1) - 1 + l * 2] == 1'b1) ?
                                                  index_nodes[2 ** (level + 1) - 1 + l * 2    ] :
                                                  index_nodes[2 ** (level + 1) - 1 + l * 2 + 1] ;
        end
      end
    end
 
end else begin: leading_cnt
 
// level: 0                                     sel[0]
//                                           /            \
// level: 1                           sel[1]            sel[2]
//                                     /     \           /     \
// level: 2                      sel[3]    sel[4]   sel[5]   sel[6]
//                                 /   \     /   \    /   \     /  \  
//                          vec_i[7]   [6] [5]  [4] [3]   [2] [1]  [0] 
//
//                      index_lut[0]   [1] [2]  [3] [4]   [5] [6]  [7] 

    for (genvar level = 0; level < IDX_W; level++) begin : g_levels
      if (level == IDX_W - 1) begin : g_last_level
        for (genvar k = 0; k < 2 ** level; k++) begin : g_iter
          // if two successive indices are still in the vector...
          if (k * 2 < WIDTH - 1) begin : g_idx_inside
            assign sel_nodes  [2 ** level - 1 + k] = vector[WIDTH-1 -k * 2   ] | 
                                                     vector[WIDTH-1 -k * 2 -1] ;
            assign index_nodes[2 ** level - 1 + k] = (vector[WIDTH-1 -k * 2] == 1'b1) ? index_lut[k * 2    ] :
                                                                                       index_lut[k * 2 + 1] ;
 
          // if only the first index is still in the vector, another index is out of vector, choose the first index.
          end else if (k * 2 == WIDTH - 1) begin : g_idx_border
            assign sel_nodes  [2 ** level - 1 + k] = vector[WIDTH-1 - k * 2];
            assign index_nodes[2 ** level - 1 + k] = index_lut[k * 2];

          // if index is out of range
          // (k * 2 > WIDTH - 1)
          end else begin : g_idx_out
            assign sel_nodes  [2 ** level - 1 + k] = 1'b0;
            assign index_nodes[2 ** level - 1 + k] = '0;
          end
        end

      end else begin : g_upper_level
        for (genvar l = 0; l < 2 ** level; l++) begin : g_iter
          assign sel_nodes[2 ** level - 1 + l] = sel_nodes[2 ** (level + 1) - 1 + l * 2    ] | 
                                                 sel_nodes[2 ** (level + 1) - 1 + l * 2 + 1] ;
          assign index_nodes[2 ** level - 1 + l] = (sel_nodes[2 ** (level + 1) - 1 + l * 2] == 1'b1) ? 
                                                    index_nodes[2 ** (level + 1) - 1 + l * 2    ] :
                                                    index_nodes[2 ** (level + 1) - 1 + l * 2 + 1] ;
        end
      end
    end
  end : leading_cnt 
 
assign cnt_o   = index_nodes[0];
assign empty_o =  ~sel_nodes[0];
 
end : gen_lzc
//==================================
// Assertions
//==================================
 
endmodule

`include "chunjun_undefine.sv" 
